package searchUtil;

/**
 * @Author: sun
 * @Description:
 * @Data: create in 15:38 2018/12/17
 * @Modfied by:
 */

import hashUtil.BBox;
import hashUtil.BBoxPrefix;
import hashUtil.GeoHashUtil;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Stack;

public class GetHashRect {
	/**
	 * 传入包含2个顶点信息的矩形，利用DFS遍历返回
	 * 一个hash 段集合。
	 *
	 * @param rectangle 有4个浮点数构成，并有逗号隔开的字符串
	 * @param deepth 递归的深度限制
	 * @return 一个Geohash 段的List
	 */
    public static ArrayList<long[]> searchRectangleByDFS(String rectangle, int deepth) {
        double bottomLeftLon, bottomLeftLat, topRightLon, topRightLat;
        String[] arr = rectangle.split(",");
        double[] pt = new double[4];
        for(int i = 0; i < 4; i++){
			pt[i] = Double.parseDouble(arr[i].trim());
		}
        //TODO 这个对于点的检查应该考虑放在构造函数中
        bottomLeftLon = Math.min(pt[0], pt[2]);//左下角经度
        bottomLeftLat = Math.min(pt[1], pt[3]);//左下角纬度
        topRightLon = Math.max(pt[0], pt[2]);//右上角经度
		topRightLat = Math.max(pt[1], pt[3]);//右上角纬度

		//结果的返回容器
        ArrayList<long[]> ResultSet = new ArrayList<long[]>();
        //searchBox，最开始的查询矩形框
        BBox searchBox = new BBox(bottomLeftLon, bottomLeftLat, topRightLon, topRightLat);
        System.out.println("searchBox "+searchBox);
        BBoxPrefix bBoxPrefix = GeoHashUtil.BBoxToPrefix(searchBox);
        Stack<BBoxPrefix> searchStack = new Stack<BBoxPrefix>();
        //DFS
        //init 将最开始的最大公共前缀放入，这里在队列中直接存储的是每个节点上对应的BBoxPrefix
        searchStack.push(bBoxPrefix);
        while (!searchStack.isEmpty()){
        	BBoxPrefix prefixNow = searchStack.pop();
            BBox prefixBBox = GeoHashUtil.PrefixToBBox(prefixNow);
            //如果被包含了，那么停止，不再继续向下搜索
            if(searchBox.contain(prefixBBox)){
                long[] hashFromTo = new long[3];
                hashFromTo[0] = prefixNow.prefix;
                hashFromTo[1] = (0xffffffffffffffffL >>> prefixNow.length) + prefixNow.prefix;
                ResultSet.add(hashFromTo);
            }else if(prefixNow.length - bBoxPrefix.length < deepth){
                //当前搜索深度比最深小的话继续压栈
                //左树1，右树0，先左后右 再判断是否超出搜索的深度
                BBoxPrefix attachOne = prefixNow.attachOne();
                BBoxPrefix attachZero = prefixNow.attachZero();
                BBox attachOneBbox = GeoHashUtil.PrefixToBBox(attachOne);
                BBox attachZeroBbox = GeoHashUtil.PrefixToBBox(attachZero);
                if(searchBox.interset(attachZeroBbox)) {
                	searchStack.push(attachZero);
                }
                if(searchBox.interset(attachOneBbox)){
                	searchStack.push(attachOne);
                }

            }else {
                //搜索深度超出范围后为了保证程序正确性直接将这个区间加入结果集
                long[] hashFromTo = new long[2];
                hashFromTo[0] = prefixNow.prefix;
                hashFromTo[1] = (0xffffffffffffffffL >>> prefixNow.length) + prefixNow.prefix;
                ResultSet.add(hashFromTo);
            }

        }
      //hash 段的排序与合并
        sortCombine(ResultSet);
        return ResultSet;
    }

    /**
     * 专门用来对hash段进行排序，以及合并。排序的规则是以hash段的开始值(即左区间值)
     * 作为排序标准，合并的规则是如果在排序之后，2个hash段合并相连(即前一个hash段的
     * 右区间值与后一个hash段的左区间值相差1)
     *
     * @param arrayList 未合并的hash段
     * @return 合并之后的hash段。
     */
    private static void sortCombine(ArrayList<long[]> arrayList){
    	//hash 段的排序
        arrayList.sort(new Comparator<long[]>() {
			@Override
			public int compare(long[] o1, long[] o2) {
				return o1[0]>o2[0]?1:(o1[0]==o2[0]?0:-1);
			}
		});
//        hash 段的合并
        for(int i = 0; i < arrayList.size()-1; i++){
        	if(arrayList.get(i)[1]+1 == arrayList.get(i+1)[0]){
        		arrayList.set(i+1,new long[]{arrayList.get(i)[0],arrayList.get(i+1)[1]});
        		arrayList.remove(i);
        		i--;
        	}
        }
    }
}